package leetcode.editor.algorithms;

import java.util.Comparator;
import java.util.PriorityQueue;

import static leetcode.editor.algorithms.QuickSort.partition;

public class SortAlgorithms {
    public static void main(String[] args) {
        int [] arr ={1,7,3,9,4,2,5,8,6,10};
//      bubbleSort(arr);
//      selectionSort(arr);
//      insertionSort(arr);
        shellSort1(arr);
        print(arr);
    }

    /**
     * 冒泡排序-升序
      * @param arr
     * @return
     */
    public static int[] bubbleSort(int [] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length-i-1; j++) {
                if (arr[j]>arr[j+1]) {
                    int temp =arr[j+1];
                    arr[j+1] = arr[j] ;
                    arr[j] = temp;
                }
            }
        }
        return arr;
    }

    /**
     * 选择排序
     * 分成排好序--未排序
     * 找到未排序的部分最小的那个索引,与未排好序的第一个交换数据
     * @param arr
     * @return
     */
    public static int[] selectionSort(int [] arr) {
        int minIndex,temp;
        for (int i = 0; i < arr.length; i++) {
            //寻找最小的数的索引,放到最前面
            minIndex = i;
            for (int j = i+1; j < arr.length; j++) {
                 if (arr[j]<arr[minIndex]) {
                     minIndex = j;
                 }
            }
            //找到最小数的索引之后,交换大小
            temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
        return arr;
    }
    /**
     * 插入排序
     * @param arr
     * @description 插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。
     * 它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
     * @return
     */
    public static int[] insertionSort(int [] arr) {
        int current,preIndex;
        //默认第一个已经排好序,不然数组越界
        for (int i = 1; i < arr.length; i++) {
            current = arr[i];
            preIndex =i-1;
            while (preIndex>=0&&arr[preIndex]>current) {
                //元素后移一位
                arr[preIndex+1] = arr[preIndex];
                preIndex--;
            }
            //注意数组下标
            arr[preIndex+1] = current;
        }
        return arr;
    }

    /**
     * 希尔排序
     * @description:1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。
     * 它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
     * 第一步:分组--第二步:用插入排序把组内的元素排好序
     * @param arr
     * @return
     */
    public static int[] shellSort(int [] arr) {
        //增量gap,并逐步缩小增量
        for (int gap = arr.length/2; gap >0; gap/=2) {
            //从第gap个元素,逐个对所在的组的进行插入排序
            for (int i = gap; i < arr.length; i++) {
                 int index = i;
                 int temp = arr[index];
                 if (arr[index] < arr[index-gap]) {
                      while (index-gap>=0&&temp<arr[index-gap]) {
                          //移动
                          arr[index] = arr[index - gap];
                          index -=gap;
                     }
                      //while退出之后,就给temp找到插入的位置
                     arr[index] = temp;
                 }
            }
        }
        return arr;
    }
    public static int[] shellSort1(int [] arr) {
        for (int gap = arr.length/2; gap >0; gap/=2) {
            for (int i = gap; i <arr.length ; i++) {
                int index =i;
                int temp = arr[index];
                if (arr[index]<arr[index-gap]) {
                    while (index-gap>=0&&arr[index-gap]>temp) {
                        arr[index] = arr[index-gap];
                        index -=gap;
                    }
                    arr[index] = temp;
                }
            }
        }
        return arr;
    }

    /**
     * 打印数组
      * @param arr
     */
    public static void print(int [] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }

    public static PriorityQueue<Integer> printQueue(int [] arr) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        for (int i = 0; i < arr.length; i++) {
              priorityQueue.add(arr[i]);
        }
        return priorityQueue;
    }
}
